#include <stdio.h>
#include <stdlib.h>

#include "automate.h"
#include "Graphe.h"

#define NON_VISITE 0
#define VISITE 1

Graphe_s* creer_graphe( void ){
	int i;
	Graphe_s* g = (Graphe_s*) malloc( sizeof(Graphe_s) );
	if (g == NULL){
	  fprintf(stderr, "Erreur lors d'allocation memoire\n");
	  exit(EXIT_FAILURE);
	}
	
	g->taille = 4;
	g->tab = (liste_s**) malloc( sizeof( liste_s* ) * g->taille );
	if (g->tab == NULL){
	  fprintf(stderr, "Erreur lors d'allocation memoire\n");
	  exit(EXIT_FAILURE);
	}
	
	for( i = 0; i < g->taille; i++){
		g->tab[i] = NULL;
	}
	return g;
}

void libere_graphe( Graphe_s **g){
	int i;
	for( i = 0; i < (*g)->taille; i++){
		libere_liste( &(*g)->tab[i] );
	}
	free( (*g)->tab );
	free( *g );
	*g = NULL;
}

void init_graphe( Graphe_s *graphe ){
	graphe->tab[0] = (liste_s* ) malloc( sizeof(liste_s) );
	if (graphe->tab[0] == NULL){
	  fprintf(stderr, "Erreur lors d'allocation memoire\n");
	  exit(EXIT_FAILURE);
	}
	
	graphe->tab[0]->state = 1;
	graphe->tab[0]->suiv = (liste_s* ) malloc( sizeof(liste_s) );
	if (graphe->tab[0]->suiv == NULL){
	  fprintf(stderr, "Erreur lors d'allocation memoire\n");
	  exit(EXIT_FAILURE);
	}
	
	
	graphe->tab[0]->suiv->state = 4;
	graphe->tab[0]->suiv->suiv = NULL;
	graphe->tab[1] = (liste_s* ) malloc( sizeof(liste_s) );
	if (graphe->tab[1] == NULL){
	  fprintf(stderr, "Erreur lors d'allocation memoire\n");
	  exit(EXIT_FAILURE);
	}
	
	graphe->tab[1]->state = 2;
	graphe->tab[1]->suiv = NULL;
	graphe->tab[2] = (liste_s* ) malloc( sizeof(liste_s) );
	if (graphe->tab[2] == NULL){
	  fprintf(stderr, "Erreur lors d'allocation memoire\n");
	  exit(EXIT_FAILURE);
	}
	
	graphe->tab[2]->state = 3;
	graphe->tab[2]->suiv = NULL;
	graphe->tab[3] = (liste_s* ) malloc( sizeof(liste_s) );
	if (graphe->tab[3] == NULL){
	  fprintf(stderr, "Erreur lors d'allocation memoire\n");
	  exit(EXIT_FAILURE);
	}
	
	graphe->tab[3]->suiv = NULL;
	graphe->tab[3]->state = 4;
}

void print_graphe( const Graphe_s const * graphe){
	int i;
	liste_s* tmp;

	for( i = 0; i < graphe->taille; i++ ){
		printf("Depuis l'etat %d on va vers: ", i);
		tmp = graphe->tab[i];
		while( tmp != NULL ){
			printf("%d ", tmp->state);
			tmp = tmp->suiv;
		}
		printf("\n");
	}
}

Graphe_s* creer_graphe_taille( const int taille ){
	int i;
	Graphe_s* g = (Graphe_s*) malloc( sizeof(Graphe_s) );
	if (g == NULL){
	  fprintf(stderr, "Erreur lors d'allocation memoire\n");
	  exit(EXIT_FAILURE);
	}
	
	g->taille = taille;
	g->tab = (liste_s**) malloc( sizeof( liste_s* ) * g->taille );
	if (g->tab == NULL){
	  fprintf(stderr, "Erreur lors d'allocation memoire\n");
	  exit(EXIT_FAILURE);
	}
	
	for( i = 0; i < g->taille; i++){
		g->tab[i] = NULL;
	}
	return g;
}

int chemin(const Graphe_s const * graphe, const int depart, const int arrivee){
	int couleur[graphe->taille];
	int i,j ;
	liste_s* tmp;

	//initialisation des couleurs
	for( i = 0; i < graphe->taille; i++){
		couleur[i] = NON_VISITE;
	}

	return search( graphe, depart, arrivee, couleur);
}

int search( const Graphe_s const *graphe, const int depart, const int arrivee, int *couleur){
	liste_s* tmp = graphe->tab[depart];
	couleur[depart] = VISITE;
	while( tmp != NULL && couleur[tmp->state] == VISITE){
		tmp = tmp->suiv;
	}

	while( tmp != NULL ){
			if( tmp->state == arrivee )
				return 1;
			else
				if( search( graphe, tmp->state, arrivee, couleur) == 1 )
					return 1;
			do{
				tmp = tmp->suiv;
			}while( tmp != NULL && couleur[tmp->state] == VISITE);
	}
	return 0;
}

Graphe_s* automateToGraphe( automate_s* a){
	Graphe_s* g = creer_graphe_taille( a->size );
	int i,j;
	liste_s *l;

	for( i = 0; i < a->size; i++ ){
		for(j = 0; j < a->sizealpha; j++){
			l = a->trans[i][j];
			while( l != NULL ){
				ajouteListe( &(g->tab[i]), l->state);
				l = l->suiv;
			}
		}
	}

	return g;
}

